package org.example.sward.tooffer;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * Copyright: 天津联想协同科技有限公司
 * <p>
 *
 * @author anlu
 * @date 2022/3/15 16:39
 */
public class Offer51 {

    int[] nums,tmp;
    public static void main(String[] args) {
        Offer51 offer51 = new Offer51();
        int[] nums = {7,5,6,4};
        int result = offer51.reversePairs(nums);
        System.out.println(result);

    }

    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0,nums.length - 1);
    }

    /**
     * 归并排序
     * @param l 左边界
     * @param r 右边界
     * @return
     */
    private int mergeSort(int l, int r) {
        //终止条件
        if(l >= r){
            return 0;
        }
        //递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l,m) + mergeSort(m + 1,r);

        //合并阶段
        //切分成2个数组后 i=左边数据的左边界  j = 右边数组的左边界
        int i = l, j = m + 1;
        for(int k = l; k <= r;k++){
            tmp[k] = nums[k];
        }
        for(int k = l; k <= r; k++){
            //说明左边数组已经遍历完了
            if(i == m+1){
                nums[k] = tmp[j++];
            }else if(j == r + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else{
                nums[k] = tmp[j++];
                //统计逆序对
                res += m - i + 1;
            }
        }
        return res;
    }

}
